<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script src="dict.js"></script>
<script src="queue.js"></script>
<script>
    //封装图结构
    function Graph(){
    //    属性：顶点（数组）/边（字典）
        this.vertexes = [] //顶点
        this.edges = new Dictionay() //边

    //    方法：
    //    添加方法：
    //    1、添加顶点的方法
        Graph.prototype.addVertex = function(v){ //往数组中添加字典
            this.vertexes.push(v)
            this.edges.set(v,[])
        }

    //    2、添加边的方法
        Graph.prototype.addEdge = function(v1,v2){ //往数组中的v1字典添加v2
            this.edges.get(v1).push(v2)
            this.edges.get(v2).push(v1)
        }

    //    3、实现toString方法
        Graph.prototype.toString = function(){
        //    1、定义字符串，保存最终的结果
            var resultString = ""

        //    2、遍历所有的顶点，以及顶点所对应的边
            for(var i=0;i < this.vertexes.length;i++){ //遍历整个数组
                resultString += this.vertexes[i] + '->' //获取数组单元中字典的key
                var vEdges = this.edges.get(this.vertexes[i])//通过key获取字典中对应的数组
                for(var x = 0;x < vEdges.length; x++){//遍历该数组
                    resultString += vEdges[x] + ' '
                }
                resultString += '\n'
            }
            return resultString
        }

    //    4、初始化状态颜色
        Graph.prototype.initializeColor = function(){
            var colors = []
            for(var i = 0; i < this.vertexes.length; i++){
                colors[this.vertexes[i]] = 'white'
            }
            return colors
        }

    //    实现广度搜索（BFS）
        Graph.prototype.bfs = function(initV,handler){
        //    1、初始化颜色
            var colors = this.initializeColor()

        //    2、创建队列
            var queue = new Queue()

        //    3、将顶点加入到队列中
            queue.enqueue(initV)

        //    4、循环从队列中取出元素
            while(!queue.isEmpty()){
            //    4.1、从队列中取出一个顶点
                var v = queue.dequeue()

            //    4.2、获取和顶点相连的另外顶点
                var vList = this.edges.get(v)

            //    4.3、将v的颜色设置成灰色
                colors[v] = 'gray'

            //    4.4、遍历所欲的顶点，并且加入到队列中
                for(var i = 0;i < vList.length;i++){
                    var e = vList(i)
                    if(colors[e] == 'white'){ //取出还未遍历的点
                        colors[e] = 'gray' //进行换色
                        queue.enqueue(e)
                    }
                }

            //    4.5、访问顶点
                handler(v)

            //    4.6、将顶点设置为黑色
                colors[v] = 'black'
            }
        }

    //    深度优先搜索（DFS）
        Graph.prototype.dfs = function(initV,handler){
        //    1、初始化颜色
            var colors = this.initializeColor()

        //    2、从某个顶点开始依次递归访问
            this.dfsVisit(initV, colors, handler)

        }

        //具体遍历方法
        Graph.prototype.dfsVisit = function(v,colors,handler){
        //    1、将颜色设置为灰色
            colors[v] = 'gray'

        //    2、处理v顶点
            handler(v)

        //    3、访问v相连的顶点
            var vList = this.edges.get(v)
            for(var i = 0;i < vList.length; i++){ //遍历与v相连顶点的数组
                var e = vList[i] //获取数组中的每个顶点
                if(colors[e] == 'white'){ //如果顶点还未进行访问
                    this.dfsVisit(e,colors,handler) //迭代
                }
            }

        //    4、将v设置成黑色
            colors[v] = 'black' //将顶点变为黑色（已遍历顶点）

        }
    }

//    测试代码
//    1、创建图结构
    var graph = new Graph()

//    2、添加顶点
    var myVertexes = ['A','B','C','D','E','F','G','H','I']
    for(var i=0;i < myVertexes.length; i++){
        graph.addVertex(myVertexes)
    }

//    3、添加边
    graph.addEdge('A','B')
    graph.addEdge('A','C')
    graph.addEdge('A','D')
    graph.addEdge('C','D')
    graph.addEdge('C','G')
    graph.addEdge('D','G')
    graph.addEdge('D','H')
    graph.addEdge('B','E')
    graph.addEdge('B','F')
    graph.addEdge('E','I')

//测试bfs
    var rewsult = ''
    graph.bfs(graph.vertexes[0],function(v){
        result += v + " "
    })
    alert(result)

//    测色dfs
    result = ''
    graph.dfs(graph.vertexes[0],function(v){
        result += v + ' '
    })

</script>
</body>
</html>